package upper02;

/**
 * 查找大于target的最小值的索引，搜索范围arr[l,r]   r=arr.length
 */
public class BinarySearch {

    public int select(int[] arr, int target) {
        return select(arr, 0, arr.length, target);
    }

    /**
     * 查找大于target的最小值的索引，搜索范围arr[l,r] r=arr.length
     * if（arr[mid]>target）r=mid;
     * if(arr[mid]<=target)l=mid+1;
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        int l = 0, r = data.length;
        //arr[l,r]中寻找解，不是一个合法的索引，但是是这个问题定义下的合法解答，这个问题中一定有问题的解答（即使没有解，也会返回data.length）
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) > 0) r = mid;
            else l = mid + 1;
        }
        return l;
    }


    /**
     * 查找大于target的最小值，搜索范围arr[l,r] r=arr.length
     * if（arr[mid]>target）r=mid;
     * if(arr[mid]<=target)l=mid+1;
     *
     * @param arr
     * @param l
     * @param r
     * @param target
     * @return
     */
    private int select(int[] arr, int l, int r, int target) {
        int mid = l + (r - l) / 2;
        if (l == r) return r;
        if (arr[mid] > target) return select(arr, l, mid, target);
        return select(arr, mid + 1, r, target);
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13};
        BinarySearch binarySearch = new BinarySearch();
        int select = binarySearch.select(arr, 11);
        System.out.println("select = " + select);
        System.out.println("arr[select] = " + arr[select]);
        Integer[] arr2 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13};
        int upper = BinarySearch.upper(arr2, 11);
        System.out.println("upper = " + upper);
        System.out.println("arr2 = " + arr2[upper]);

        System.out.println();

        Integer[] arr3 = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i <= 6; i++) System.out.print(BinarySearch.upper(arr3,i)+" ");
        System.out.println();
    }
}
